package ljl.alg.jianzhioffer.round3.easy;

import commons.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class _7_build_tree {
    
    int[] pre;
    Map<Integer, Integer> inPos = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        pre = preorder;
        for (int i = 0; i < inorder.length; i++) {
            inPos.put(inorder[i], i);
        }
        return build(0, 0, inorder.length - 1);
    }
    TreeNode build(int root, int left, int right) {
        if (left > right) return null;
        int rootPos = inPos.get(pre[root]);
        TreeNode res = new TreeNode(pre[root]);
        res.left = build(root + 1, left, rootPos - 1);
        res.right = build(root + 1 + rootPos - left, rootPos + 1, right);
        return res;
    }
}
